// 有一些工作：difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
// 现在我们有一些工人。worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。
// 每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。

// 举个例子，如果 3 个工人都尝试完成一份报酬为 1 的同样工作，那么总收益为 $3。
// 如果一个工人不能完成任何工作，他的收益为 $0 。
// 我们能得到的最大收益是多少？

// 示例：
// 输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
// 输出: 100 
// 解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

// 提示:
//     1 <= difficulty.length = profit.length <= 10000
//     1 <= worker.length <= 10000
//     difficulty[i], profit[i], worker[i]  的范围是 [1, 10^5]

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
///////最容易想到的就是双重循环暴力解法，不过leetcode超时
///// 用到了贪心思想：局部最优-->全部最优。。排序+双指针
var maxProfitAssignment = function(difficulty, profit, worker) {
    let map = new Map();
    for(let i = 0; i < difficulty.length; i++) {
        map.set(difficulty[i], profit[i]);
    }
    let mapArray = Array.from(map);
    mapArray.sort((a, b)=>{
        return a[0] - b[0];
    });
    worker.sort((a, b)=>{
        return a - b;
    });
    let mapArrayIndex = 0, workerIndex = 0, maxProfit = 0, result = 0;
    while(mapArrayIndex < mapArray.length && workerIndex < worker.length) {
        
        if (mapArray[mapArrayIndex][0] <= worker[workerIndex]) {
            maxProfit = Math.max(maxProfit, mapArray[mapArrayIndex][1]);
            mapArrayIndex++;
        } else {
            result += maxProfit;
            workerIndex++;

        }
    }
    result += (worker.length - workerIndex) * maxProfit;
    return result;
};
console.log(maxProfitAssignment([66,1,28,73,53,35,45,60,100,44,59,94,27,88,7,18,83,18,72,63],
    [66,20,84,81,56,40,37,82,53,45,43,96,67,27,12,54,98,19,47,77],
    [61,33,68,38,63,45,1,10,53,23,66,70,14,51,94,18,28,78,100,16]
    ));